package 我的Java学习_算法基础.day_08;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @date 2021/8/26 - 08 - 26 - 7:40
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */

/**
 *
 * Input:
 * 5
 *     7
 *    3 8
 *   8 1 0
 *  2 7 4 4
 * 4 5 2 6 5
 * Output:
 * 30
 */
public class _134_数字三角形 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] triangle =  new int[n][];
        for(int i =0;i<n;i++){
            triangle[i] = new int[i+1];
            for (int j = 0; j < i + 1; j++) {
                triangle[i][j] = sc.nextInt();
            }
        }
        System.out.println(recursion(triangle,0,0));
        System.out.println(memoryRecursion(triangle,0,0));
        System.out.println(dp(triangle,0,0));
        System.out.println(dp1(triangle));

    }
    private static int recursion(int[][] triangle,int i,int j){
        int rowIndex = triangle.length;
        if(i==rowIndex-1){
            return triangle[i][j];
        }else {
            //顶点的值+max(左侧支线的最大值，右侧支路最大值)
            return triangle[i][j]+
                    Math.max(recursion(triangle,i+1,j),
                            recursion(triangle,i+1,j+1));
        }
    }
    static int[][] map;
    private static int memoryRecursion(int[][] triangle,int i,int j){
        int rowCount = triangle.length;
        int columnCount = triangle[rowCount-1].length;
        map = new int[rowCount][columnCount];
        int value = triangle[i][j];
        if(i!=rowCount-1){  //不是最后一行
            //储存有值，就不递归
            int v1 = map[i+1][j];
            if(v1==0)
                v1 = memoryRecursion(triangle,i+1,j);
            int v2 = map[i+1][j+1];
            if(v2==0)
                v2 = memoryRecursion(triangle,i+1,j+1);
            value = value +Math.max(v1,v2);
        }
        //存入表
        map[i][j] = value;
        return value;
    }
    private static int dp(int[][] triangle,int i,int j){
        int rowCount = triangle.length;
        int columnCount = triangle[rowCount-1].length;
        map = new int[rowCount][columnCount];
        //初始化最后一行
        for(int k = 0;k<columnCount;k++){
            map[rowCount-1][k] = triangle[rowCount-1][k];
        }
        //从倒数第二行开始，由底向上递推
        for(int k =rowCount-2;k>=0;k--){
            for (int l = 0; l <=k ; l++) {
                //当前值加上左右支路最大值
                map[k][l] = triangle[k][l]+Math.max(map[k+1][l],map[k+1][l+1]);
            }
        }
        return map[i][j];
    }
    //求从顶到底路径最大和，二维表可改为一维表，节约内存
    static int[] dpMap;
    private static int dp1(int[][] triangle){
        int colCount = triangle.length;
        int columnCount = triangle[colCount-1].length; //最后一行列数
        dpMap =  new int[columnCount];
        //初始化，赋予最后一行值
        for (int i = 0; i < columnCount; i++) {
            dpMap[i]=triangle[colCount-1][i];
        }
        //从倒数第二行开始递推
        for (int i = colCount-2; i >=0; i--) {
            for (int j = 0; j < triangle[i].length; j++) {
                dpMap[j] = triangle[i][j]+Math.max(dpMap[j],dpMap[j+1]);
            }
        }
        return dpMap[0];
    }
}
